package com.wtgroup.demo.面试题.我的面试.字节;

import com.wtgroup.demo.mianshi.算法.二叉树.model.Node;
import org.junit.Test;

/**
 * 判断路径和是否有 22
 * <p>
 * 2021年5月17日 面试
 *
 * 路径是从根到叶子经过节点值的和，判断二叉树中是否有一个路径上的数字之和等于给定的数字22
 *
 * 5
 *
 * / \
 *
 * 4   8
 *
 * /     / \
 *
 * 11  13  4
 *
 * /  \         \
 *
 * 7    2      1
 * @author 60906
 * @date 2021/5/17 23:07
 */
public class Q_二叉树路径和 {
    @Test
    public void test1() {
        int[] datas = {5, 4, 8, 11, 13, 4, 7, 2};
        Node<Integer> root = new Node<>(5);
        Node<Integer> n1 = new Node<>(4);
        Node<Integer> n2 = new Node<>(8);
        root.left = n1; root.right = n2;
        Node<Integer> n3 = new Node<>(11);
        n1.left = n3;
        Node<Integer> n4 = new Node<>(13);
        n2.left = n4;
        Node<Integer> n5 = new Node<>(4);
        n2.right = n5;
        Node<Integer> n6 = new Node<>(7);
        n3.left = n6;
        Node<Integer> n7 = new Node<>(2);
        n3.right = n7;

        boolean res = new Solution_1().run(root);
        System.out.println(res);
    }


    class Solution_1 {

        // 回溯
        boolean run(Node<Integer> root) {

            return func(0, root);
        }

        boolean func(int path, Node<Integer> parent) {
            if (parent == null) {
                return path == 22 ? true : false;
            }

            // 1 + (n-1)
            path += parent.data;
            boolean left = func(path, parent.left);
            if (left) {
                return true;
            } else {
                return func(path, parent.right);
            }
        }

    }

    class S20250301 {
        public void x(Node<Integer> head) {
            // 目标 t
            // 当前节点值 x
            // 左子树有没有 t-x 的路径?
            // 否, 则看子树有没有 t-x 的路径?
            // 剪枝: 当前值已经>=t, 不用往下递归了

        }
    }

}
